package backtrack

var phoneMap map[string]string = map[string]string{
	"2": "abc",
	"3": "def",
	"4": "ghi",
	"5": "jkl",
	"6": "mno",
	"7": "pqrs",
	"8": "tuv",
	"9": "wxyz",
}

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	res := make([]string, 0)
	path := []byte{}
	var dfs func(int)
	dfs = func(index int) {
		if index == len(digits) {
			res = append(res, string(path))
			return
		}
		num := digits[index]
		for i := 0; i < len(phoneMap[string(num)]); i++ {
			path = append(path, phoneMap[string(num)][i])
			dfs(index + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return res
}
